package may.test_5_12;

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length + 1];
        int ret = Integer.MIN_VALUE;
        for (int  i = 1; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1],dp[i - 1] + nums[i - 1]);
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
    public int maxSubarraySumCircular(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        int sum = 0;
        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            f[i] = Math.max(x, x + f[i - 1]);
            fmax = Math.max(fmax, f[i]);
            g[i] = Math.min(x, x + g[i - 1]);
            gmin = Math.min(gmin, g[i]);
            sum += x;
        }
        return sum == gmin ? fmax : Math.max(fmax, sum - gmin);
    }
    public int maxProduct1(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n;i++) {
            int x = i - 1;
            fmax = Math.max(nums[x] * g[i - 1],nums[x] * f[i - 1]);
            f[i] = Math.max(nums[x],fmax);
            gmin = Math.min(nums[x] * f[i - 1],nums[x] * g[i-1]);
            g[i] = Math.min(gmin,nums[x]);
            max = Math.max(f[i],max);
        }
        return max;
  }
    public int maxProduct(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = 1;
        g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int y = f[i - 1] * nums[i - 1];
            int z = g[i - 1] * nums[i - 1];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }
}
